# -*- coding: utf-8 -*-
"""
作者: liuzaiqiang
邮箱: zaiqiangliu@163.com
地址: 新疆大学
创建时间: 2025/11/14 20:56
功能描述:

题目背景：
    作为研究生，你需要高效地安排自己的时间，比如参加一系列学术讲座。每个讲座都有一个开始时间和结束时间。为了能听到尽可能多的完整讲座，你需要制定一个最优的听讲座策略。
题目描述：
    给定一个包含多个讲座的列表，每个讲座由其开始时间和结束时间表示，例如 [(start1, end1),(start2, end2), ...] 。
    请编写一个函数 select_lectures ，找出你可以参加的最多讲座数量，并返回这个数量。假设你在同一时间只能参加一个讲座。
要求：
    1. 你需要运用贪心算法的思想来解决问题。
    2. 在实现过程中，请尽量使用函数式编程的风格，例如使用 lambda 函数进行排序，或使用列表推导式/高阶函数处理数据。


“最多不重叠讲座” 问题没有通用数学公式，但贪心算法（按结束时间排序 + 依次选择不重叠） 是最优且高效的解法，逻辑简单到几乎等同于 “公式级” 的直接求解，
实际应用中可快速得到结果。


"""

from typing import List, Tuple

#Tuple[int, int]:  [int, int] 表示这个元组有且仅有两个元素，且每个元素的类型都是 int（整数）。
def select_lectures(lectures: List[Tuple[int, int]]) -> int:
    """
    计算可以参加的最多讲座数量。
    lectures: 一个元组列表，每个元组 (start, end) 代表一个讲座的起止时间。
    """
    if not lectures:
        return 0
    # 贪心策略的关键：按结束时间对所有讲座进行升序排序。
    # 这里使用了 sorted 函数和 lambda 表达式，体现了函数式编程的简洁性。
    # lambda lecture: lecture[1] 定义了一个匿名函数，用于提取元组的第二个元素（结束时间）作为排序依据。

    #sorted() 是 Python 内置函数，用于对可迭代对象（如列表）进行排序，返回一个新的排序后列表（不修改原列表）。
    #key 参数接收一个函数
    #lambda lecture: lecture[1]：这是一个匿名函数（lambda 函数），作用是从元素中提取排序关键字。
    #lambda 是定义匿名函数的关键字，语法为 lambda 参数: 返回值。
    # 这里的 lecture 是参数，表示 lectures 列表中的单个元素（例如一个 (开始时间, 结束时间) 元组）。
    # lecture[1] 是返回值，表示取这个元素（元组）的第二个值（因为 Python 索引从 0 开始，[1] 对应第二个元素）。
    #总结：逻辑链是：遍历 lectures 中的每个元素（lecture）；对每个元素，用 lambda 函数提取 lecture[1]（第二个值）作为排序关键字；按关键字从小到大对元素排序，返回新列表。
    sorted_lectures = sorted(lectures, key=lambda lecture: lecture[1])
    count = 0
    last_end_time = -1 # 初始化一个非常早的结束时间
    # 遍历排序后的讲座列表
    for start, end in sorted_lectures:
        # 如果当前讲座的开始时间晚于或等于上一个已选讲座的结束时间，说明它们不冲突，可以选择这个讲座。
        if start >= last_end_time:
            count += 1
            last_end_time = end # 更新最后一个讲座的结束时间
    return count
# 测试代码
if __name__ == '__main__':
    # (开始时间, 结束时间)
    lectures = [
                [],
                [(1, 2)],
                [(1, 10), (2, 3), (4, 5)],
                [(1, 5), (2, 3), (3, 4)],
                [(1, 2), (2, 3), (3, 4)],
                [(1, 4), (5, 6), (7, 8)],
                [(1, 10), (2, 8), (3, 6)],
                [(1, 3), (1, 3), (1, 3)],
                [(1, 5), (6, 10), (3, 7), (2, 8)],
                [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8,
                12), (2, 13), (12, 14)],
                [(1, 100), (2, 3), (4, 5), (6, 7), (8, 9)]
                ]
    for lec in lectures:
        print(f"{lec},可以参加的最多的讲座数量是：{select_lectures(lec)}")

"""
[],可以参加的最多的讲座数量是：0
[(1, 2)],可以参加的最多的讲座数量是：1
[(1, 10), (2, 3), (4, 5)],可以参加的最多的讲座数量是：2
[(1, 5), (2, 3), (3, 4)],可以参加的最多的讲座数量是：2
[(1, 2), (2, 3), (3, 4)],可以参加的最多的讲座数量是：3
[(1, 4), (5, 6), (7, 8)],可以参加的最多的讲座数量是：3
[(1, 10), (2, 8), (3, 6)],可以参加的最多的讲座数量是：1
[(1, 3), (1, 3), (1, 3)],可以参加的最多的讲座数量是：1
[(1, 5), (6, 10), (3, 7), (2, 8)],可以参加的最多的讲座数量是：2
[(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14)],可以参加的最多的讲座数量是：4
[(1, 100), (2, 3), (4, 5), (6, 7), (8, 9)],可以参加的最多的讲座数量是：4
"""